#define _CRT_SECURE_NO_WARNINGS 1

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    struct ListNode* middleNode(struct ListNode* head)
    {
        struct ListNode* fast = head, * slow = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    struct ListNode* reverse(struct ListNode* head)
    {
        struct ListNode* pcur = head;
        struct ListNode* newnode = NULL;
        while (pcur)
        {
            struct ListNode* next = pcur->next;
            pcur->next = newnode;
            newnode = pcur;
            pcur = next;
        }
        return newnode;
    }

    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* mid = middleNode(A);
        struct ListNode* reve = reverse(mid);
        while (A && reve)
        {
            if (A->val != reve->val)
                return false;

            A = A->next;
            reve = reve->next;
        }
        return true;
    }
};